#ifndef LIST_H
#define LIST_H
	//#include <windows.h>
	#include "Node.h"

    using namespace std;
    template<class TYPE>
    class List
    {
        public:
            List();
            ~List();
            unsigned int getSize();

            void pushFront(TYPE data);
            void pushBack(TYPE data);

            void popFront();
            void popBack();

            TYPE removeElementAt(int index);
            TYPE removeElement(TYPE value);
            TYPE removeFirst();

            TYPE sInsert(TYPE data);
            TYPE tInsert(TYPE data);
            TYPE insert(TYPE data);
            void remove(TYPE data, bool type);

            bool find(TYPE data);
            bool findRecursive (TYPE data);
            bool findRecursive(TYPE data, Node<TYPE>* cursor);

            bool isEmpty(){return this->lenght==0;}

            friend ostream& operator<<(ostream& outStream, const List& object);

            void clear();
            void callclearRecursive();
            void clearRecursive(Node<TYPE>*& cursor);

            void sort();
            void swap(Node<TYPE>* cursor1, Node<TYPE>* cursor2);
            void print();

            //void setHead(Node<TYPE>* head);
            Node<TYPE>* getHead()const;
            Node<TYPE>*& getHead();

			//void setNode(int i,Node<TYPE>* head);
            Node<TYPE>* getNode(int index)const;
            Node<TYPE>*& getNode(int index);

            //void setTail(Node<TYPE>* tail);
            Node<TYPE>* getTail()const ;
            Node<TYPE>*& getTail();

        private:
            unsigned int lenght;
            Node<TYPE>* head;
            Node<TYPE>* tail;

    };

    /*template<class TYPE>
    void List<TYPE>::setHead(Node<TYPE>* head)
    {
        this->head =head;
    }*/

    template<class TYPE>
    Node<TYPE>* List<TYPE>::getHead()const
    {
        return this->head;
    }

    template<class TYPE>
    Node<TYPE>*& List<TYPE>::getHead()
    {
        return this->head;
    }

	template<class TYPE>
    Node<TYPE>* List<TYPE>::getNode(int index)const
    {
		if(index > lenght){
			return NULL;
		}else if(index<=0){
			return this->head;
		}else{
			Node<TYPE>* cursor = this->head;//i=0
			for(int i=0;i<index;i++){
				cursor=cursor->getNext();
			}
			return cursor;
		}
    }

    template<class TYPE>
    Node<TYPE>*& List<TYPE>::getNode(int index)
    {
		if(index > lenght){
			return NULL;
		}else if(index<=0){
			return this->head;
		}else{
			Node<TYPE>* cursor = this->head;//i=0
			for(int i=0;i<index;i++){
				cursor=cursor->getNext();
			}
			return cursor;
		}
    }

    /*template<class TYPE>
    void List<TYPE>::setTail(Node<TYPE>* tail)
    {
        this->tail = tail;
    }*/

    template<class TYPE>
    Node<TYPE>* List<TYPE>::getTail()const
    {
        return this->tail;
    }

    template<class TYPE>
    Node<TYPE>*& List<TYPE>::getTail()
    {
        return this->tail;
    }

    template<class TYPE>
    List<TYPE>::List()
    {
        this->lenght=0;
        this->head=NULL;
        this->tail=NULL;
    }

    template<class TYPE>
    List<TYPE>::~List()
    {

    }

    template<class TYPE>
    unsigned int List<TYPE>::getSize()
    {
        return this->lenght;
    }

    template<class TYPE>
    void List<TYPE>::pushFront(TYPE data)
    {
        Node<TYPE> *newNode = new Node<TYPE>(data);
        if(this->head==NULL && this->tail ==NULL)
        {
            this->tail =this->head=newNode;
        }
        else
        {
            this->head->setPrevious(newNode);
            newNode->setNext(this->head);
            this->head=newNode;
        }
        this->lenght++;
    }

    template<class TYPE>
    void List<TYPE>::pushBack(TYPE data)
    {
        Node<TYPE>* newNode = new Node<TYPE>(data);
        if(this->head==NULL && this->tail == NULL)
        {
            this->tail = this->head = newNode;
        }
        else
        {
            this->tail->setNext(newNode);
            newNode->setPrevious(this->tail);
            this->tail = newNode;
            this->tail ->setNext(NULL);
        }
        this->lenght++;
    }

    template<class TYPE>
    void List<TYPE>::popFront()
    {
        if(this->head!=NULL)
        {
            Node<TYPE> *tmp= this->head;
            this->head = this->head->getNext();
            if(this->tail==tmp)
            {
                this->tail=NULL;
            }
            else
            {
                this->head->setPrevious(NULL);
            }
            delete tmp;
            this->lenght--;
        }
    }

    template<class TYPE>
    void List<TYPE>::popBack()
    {
        if(this->tail!=NULL)
        {
            Node<TYPE>* tmp = this->tail;
            this->tail=this->tail->getPrevious();
            if(this->head==tmp)
            {
                this->head=NULL;
            }
            else if(this->head!=tmp)
            {
                this->tail->setNext(NULL);
            }
            delete tmp;
            this->lenght--;
        }
    }

    template<class TYPE>
    TYPE List<TYPE>::sInsert(TYPE data)
    {
        Node<TYPE>* newNode = new Node<TYPE>(data);
        if(this->head==NULL && this->tail ==NULL)
        {
            this->head = this->tail = newNode;
        }
        else if(this->head->getData() > data)
        {
            newNode->setNext(this->head);
            this->head->setPrevious(newNode);
            this->head = newNode;
        }
        else if(this->tail ->getData()<=data)
        {
            this->tail->setNext(newNode);
            newNode->setPrevious(this->tail);
            this->tail = newNode;
        }
        else
        {
            Node<TYPE>* cursor = this->head;
            while(cursor->getNext()!=NULL && cursor->getNext()->getData()<data)
            {
                cursor = cursor->getNext();
            }
            cursor->getNext()->setPrevious(newNode);
            newNode->setNext(cursor->getNext());
            cursor->setNext(newNode);
            newNode->setPrevious(cursor);
        }
        this->lenght++;
        return data;
    }

    template<class TYPE>
    TYPE List<TYPE>::insert(TYPE data)
    {
        Node<TYPE>* newNode = new Node<TYPE>(data);
        if(this->head==NULL && this->tail ==NULL)
        {
            this->head = this->tail = newNode;
        }
        else
        {
            newNode->setNext(this->head);
            this->head->setPrevious(newNode);
            this->head = newNode;
        }
        this->lenght++;
        return data;
    }

    template<class TYPE>
    TYPE List<TYPE>::tInsert(TYPE data)
    {
        Node<TYPE>* newNode = new Node<TYPE>(data);
        if(this->head==NULL && this->tail ==NULL)
        {
            this->head = this->tail = newNode;
        }
        else
        {
            this->tail->setNext(newNode);
            newNode->setPrevious(this->tail);
            this->tail = newNode;
        }
        this->lenght++;
        return data;
    }


    template<class TYPE>
    void List<TYPE>::sort()
    {
        if(this->head!=NULL)
        {
            bool sort =false;
            for(int i=0; i<this->lenght && sort!=true; i++)
            {
                Node<TYPE>* cursor=this->tail;
                for(int j=this->lenght-1; j>i; j--)
                {
                    if(cursor->getData()<cursor->getPrevious()->getData())
                    {
                        sort = false;
                        swap(cursor, cursor->getPrevious());
                    }
                    cursor = cursor->getPrevious();
                }
            }
        }
    }
    template<class TYPE>
    void List<TYPE>::swap(Node<TYPE> *cursor1, Node<TYPE> *cursor2)
    {
        int tmp;
        tmp = cursor1->getData();
        cursor1->setData(cursor2->getData());
        cursor2->setData(tmp);
    }
    template<class TYPE>
    bool List<TYPE>::find(TYPE data)
    {
        if(this->head==NULL && this->tail ==NULL)
        {
            return false;
        }
        Node<TYPE>* cursor = this->head;
        while(cursor!=NULL && cursor->getData()!=data)
        {
            cursor = cursor->getNext();
        }
        if(cursor==NULL)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    template<class TYPE>
    bool List<TYPE>::findRecursive (TYPE data)
    {
        return findRecursive(data, this->head);
    }
    template<class TYPE>
    bool List<TYPE>::findRecursive(TYPE data, Node<TYPE>* target)
    {
        if(target==NULL)
        {
            return false;
        }
        else if(target->getData()==data)
        {
            return true;
        }
        else
        {
            return findRecursive(data, target->getNext());
        }
    }
    template<class TYPE>
    ostream& operator<<(ostream& outStream, const List<TYPE>& object)
    {
        for(Node<TYPE>* cursor = object.head; cursor ; cursor= cursor->getNext())
        {
            outStream<<cursor->getData();
        }
        outStream<<endl;
        return outStream;
    }
    template<class TYPE>
    void List<TYPE>::clear()
    {
        while(this->head!=NULL)
        {
            Node<TYPE>* tmp =this->head;
            this->head = this->head->getNext();
            delete tmp;
        }
        this->tail = NULL;
    }
    template<class TYPE>
    void List<TYPE>::callclearRecursive()
    {
        clearRecursive(this->head);
        this->head=NULL;
        this->tail=NULL;
    }
    template<class TYPE>
    void List<TYPE>::clearRecursive(Node<TYPE> *&cursor)
    {
        if(cursor!=NULL)
        {
            clearRecursive(cursor->getNext());
            delete cursor;
            cursor = NULL;
        }
    }
    template<class TYPE>
    void List<TYPE>::print()
    {
        Node<TYPE>* cursor=this->head;
        cout<<"Double Linked-List<TYPE>:" << endl;
        for(int i=1;cursor!=NULL;i++)
        {
            cout<<"["<<i<<"]"<<cursor->getData()<<"->";
            cursor=cursor->getNext();
        }
        cout<<endl;
    }

    template<class TYPE>
    TYPE List<TYPE>::removeElementAt(int index){
		if(index > lenght){
			return NULL;
		}else if(index<=0){
			return this->removeFirst();
		}else{
			TYPE data;
			Node<TYPE>* cursor = this->head;//i=0
			for(int i=0;i<index;i++){
				cursor=cursor->getNext();
			}
			data=cursor->getData();

			Node<TYPE> *previous = cursor->getPrevious();
			Node<TYPE> *next = cursor->getNext();
			previous->setNext(next);
			next->setPrevious(previous);

			delete cursor;
			this->lenght--;
			return data;
		}
}

    template<class TYPE>
    TYPE List<TYPE>::removeElement(TYPE value){
        if(isEmpty()){
            return NULL;
        }else{
            TYPE data;
            Node<TYPE>* cursor = this->head;//i=0
            data=cursor->getData();
            int i=0;
            while(cursor!=NULL && data!=value){
                cursor=cursor->getNext();
                data=cursor->getData();
            }
            if(data!=value){
                return NULL;
            }else{
                Node<TYPE> *previous = cursor->getPrevious();
                Node<TYPE> *next = cursor->getNext();
                previous->setNext(next);
                next->setPrevious(previous);

                delete cursor;
                this->lenght--;
                return data;
            }
        }
    }

    template<class TYPE>
    TYPE List<TYPE>::removeFirst(){
        if(!isEmpty()){
            TYPE data=this->head->getData();
            Node<TYPE> *temp= this->head;
            this->head = this->head->getNext();
            if(this->tail==temp)
            {
                this->tail=NULL;
            }
            else
            {
                this->head->setPrevious(NULL);
            }
            delete temp;
            this->lenght--;
            return data;
        }
        return NULL;
    }

#endif // LIST_H